import javax.lang.model.element.NestingKind;
import java.util.*;

/**
 * @author ZCR
 * @create 2025/9/4 00:09
 */
public class Solution752 {
    public String moveUp(String s, int index) {
        char[] temp = s.toCharArray();
        if (temp[index] == '9') {
            temp[index] = '0';
        } else {
            temp[index] += 1;
        }
        return new String(temp);
    }

    public String moveDown(String s, int index) {
        char[] temp = s.toCharArray();
        if (temp[index] == '0') {
            temp[index] = '9';
        } else {
            temp[index] -= 1;
        }
        return new String(temp);
    }

    public int openLock(String[] deadends, String target) {
        String start = "0000";
        if (start.equals(target)) {
            return 0;
        }
        Set<String> deadSet = new HashSet<>(Arrays.asList(deadends));
        if (deadSet.contains(start)) {
            return -1;
        }
        Set<String> visited = new HashSet<>();
        Queue<String> queue = new LinkedList<>();
        queue.add(start);
        visited.add(start);
        int step = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            step++;
            for (int i = 0; i < size; i++) {
                String cur = queue.poll();
                if (cur.equals(target)) {
                    return step - 1;
                }
                for (int j = 0; j < 4; j++) {
                    String next1 = moveUp(cur, j);
                    String next2 = moveDown(cur, j);
                    if (!deadSet.contains(next1) && !visited.contains(next1)) {
                        queue.add(next1);
                        visited.add(next1);
                    }
                    if (!deadSet.contains(next2) && !visited.contains(next2)) {
                        queue.add(next2);
                        visited.add(next2);
                    }
                }

            }
        }
        return -1;
    }

    public static void main(String[] args) {
        Solution752 solution = new Solution752();
        System.out.println(solution.openLock(new String[]{"0201", "0101", "0102", "1212", "2002"}, "0202"));
        System.out.println(solution.openLock(new String[]{"8888"}, "0009"));
        System.out.println(solution.openLock(new String[]{"8887", "8889", "8878", "8898", "8788", "8988", "7888", "9888"}, "8888"));
    }
}
